Corelab Seminar
2013-2014
Dimitris Chatzidimitriou (UoA)
Recognizing Subgraphs of Grids is NP-Complete
Abstract.
A graph H that can be obtained from a graph G by successively removing either one of its vertices or one of its edges is called a subgraph of
G. Other relations between graphs such as the minor and the induced
minor relationship are well studied and the corresponding problems of
recognizing whether a graph is a minor of another is shown to be in
P, while for induced minors is FPT. On the other hand, the subgraph
relation seems to be more difficult to recognize since the corresponding
general problem is in NP. In this talk we will show that the much more
specific problem of recognizing whether a given graph is a subgraph of
a (large enough) grid is also in NP.